大致题意:给你一个字符串,问这个字符串的子串中,有多少个本质不同的回文串恰好是另外一个回文串的子串,求这样的回文串的对数。 可以说,这是一个回文树/回文自动机的裸题吧。显然,在回文树里面,一个节点的...
大致题意:给你一个字符串,问这个字符串的子串中,有多少个本质不同的回文串恰好是另外一个回文串的子串,求这样的回文串的对数。 可以说,这是一个回文树/回文自动机的裸题吧。显然,在回文树里面,一个节点的...
大致题意:告诉你范围A和B,让你求在两个范围内,有多少对数字可以使得二者按位与大于C或者异或小于C。 一个比较常规的数位dp,然而比赛的时候由于自己复杂度计算错误,还写了好久的优化,最后发现不优化也能过。...
题解
题目链接:... 题意:给出n种树和n个h[i],c[i],p[i]代表每种树的高度,砍掉一棵的花费,树的个数。现在要求砍掉一部分树,使得最高的树的个数大于总树木的一半。 数据范围:1<=n<=1e5,1<...=1e9...
这题一直忘了补。。。今天没比赛刚好补了 比赛的时候看见以为是撒高级数论计数题,然而怎么过了这么多人,最后没想到是数位DP。 我们知道对于位运算来说,当高位&...C,那么就一定能被算进答案里了。...
题目链接 题意:在一个n*n的二维空间上有任意个气球,你可以横着发射三发子弹,竖着发射三发子弹,且要求每连续两发子弹的间距要恰好等于r。每发子弹可以打掉一排或者一列的气球,问你最多可以打掉多少个气球。...
2020牛客多校暑期集训营第八场题解.pdf
题意:给定n个点m条无向边,每条边有四个参数,两个端点编号,还有一个size的范围l,r。有多少合法的size可以从1走到n。 数据范围:1<=n,m<=1e5,1<...思路:首先对size离散化左端点...
题意:问能不能将三角形放在矩形内 题解:让一个顶点在原点,另一条边卡在墙角上,分别枚举是哪条边卡在上面 虽然题目说1e-6精度以上的会被忽略。。。但是我输出.6f就是不行。。。得.10f才够 ...
题意:给你一个,,构造一个的矩阵,矩阵由和组成,并且矩阵的任意两行相乘的和为0。 思路:首先 时的答案已经知道,考虑用 构造出 的解,不妨设方阵为 的解,那么下面这个方阵则是 的一个解:。...
首先,可以按位考虑,对于第i位有多少个m的倍数满足这一位上为1? 对于一个数x,我们判断这一位上是否为1,参考十进制的做法,即 ; 那么将公式变一下型: 后半部分是一个等差数列整除一个整数的求和式。...
题意:给出一个空集合,每次给出一个l,r的区间将l,r的这些数全部扔进区间内,每次要求输出此时的中位数是多少,若是集合是偶数个数则输出小的那个中位数。 数据范围:1<=N,l,r<=4e5 ...思路:首先离散化一下...
题意: 初始有n个技能,初始等级为0,有1~m m个技能等级,升级需要成本,当n个技能都升级到某个等级以上就会给予奖励 升级的成本和给予的奖励可能为负数,请问得到最大利润的状态下的利润是多少 ...
大致题意:给你n个数字,然后让你求所有满足异或和为0的子集的大小之和。 首先这个子集大小之和,显然可以转换为计算每个数字的出现次数之和。考虑到异或和为0的子集,相当于可以用集合中的一部分数字去表示另外一...
大致题意:告诉你一个n和m,让你求。 涉及到位运算的东西,很容易想到计算贡献,这里也是一样。因为最后按位与的是一个常数,所以只需要看这个常数对应为1的位置,在M、2M、3M...NM这N个数字中,有多少个仍然是1。...
题目传送门 大致题意: 输入整数n(1<=n<=100000),再输入由n个0或1组成的字符串,求该字符串中满足1和0个数相等的最长子串、子序列。 sample input: ...补充一下子串和子序列的区别:字串必须连续,子序列...
"蔚来杯"2022牛客暑期多校训练营1
链接:https://ac.nowcoder.com/acm/contest/884/A 来源:牛客网 题目描述 A new city has just been built. There'ren interesting places numbered by positive numbers ... In order to save resources, only...
大致题意:给你一棵树,每个点上有一个点权,让你找三条不相交的链,使得这三条链的权值和最大。 ...典型的树形dp,但是状态不太好表示。很容易想到,令dp[i][j]表示在点i以及对应子树里面取了j条链的最大...
题意: 给你2个长度为n的区间 a区间和b区间 ...南昌邀请赛 I题原题QAQ 记录下a数组每个点以他为最小值的区间最左边是哪个点,最右边是哪个点,用单调栈进行操作 r[i]表示右边界 l[i]表示左边界 用线段树维护前缀...
题意: 给你一个n*m的只有 1 和 0 的矩阵, 求全是1的第二大的子矩阵的面积。...比赛后看到有人用暴力写法A过了,惊了,我copy了他的代码交了一发,tle,牛客的服务器让我觉得好迷 然后看了队友的单调栈写法发...
题目大意:给出一个长度为 n 的数列 a ,规定函数 f( l , r ) = a[ l ] & a[ l + 1 ] & ...... a[ r ] ,在规定sets( l , r ) = { f( a , b ) | l <= a <= b <= r } ,对于 q 次询问,每次询问回答 s...
标签: c++
A Singing Contest 时间限制:11 秒 内存限制: 256M Jigglypuff is holding a singing contest. There are 2 n singers indexed from 1 to 2 n participating in the...contest. The rule of this contest is l...
大致题意:给你一个n*m的矩阵,每一个位置可以填0、1和2三个数字,...其实问题也很明显,这个问题不满足后效性,计算出来的方案数会比实际的方案数要多。那么我们就得换一个思路去思考这个问题。注...
B.Basic Gcd Problem www我的锅,一直以为1返回的是c没有特判,直到队友问了才发现QAQ 就是简单的快数幂 代码: #include<bits/stdc++.h> using namespace std; #define ll long long ... while(n)
4. Chiaki has an n x n matrix. She would like to fill each entry by -1, 0 or 1 such that r1,r2,...,rn,c1,c2, ..., cn are distinct values, where ri be the sum of the i-th row and c i be the...